题解 CF1148F@洛谷 | 1148F@Codeforces 【Foo Fighters】

有点毒瘤的贪心题，当然也可能是我太菜了。

翻译的挺清楚的了，直接说思路：

我们考虑在读入时顺便把每个数的 $mask$ 权值的二进制最高位预处理出来，同时统计权值和。由于正数变负数和负数变正数本质上是一样的，为了方便考虑，如果 $val$ 权值和为负数，将所有 $val$ 取相反数。

随后考虑如何贪心：

枚举每一位，统计二进制最高位为该位的所有数的 $val$ 权值和。如果这个权值和小于或等于零，那么没有修改该位的必要，因为修改不会使总权值增加，反而可能减少。如果最高位为该位的权值和大于零，那么修改该位比不修改更优。在答案变量中将该位置为 $1$，并且枚举所有数修改即可。

以上为正解，复杂度 $O(n\log{x})$，$x$ 为变量范围（$2^{62}-1$）。

坑点：贪心时必须从低位到高位枚举每一位进行更新，否则后面的更改可能导致更高位的决策被干扰，得不到正确答案！

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5+5, bit = 62;

ll n, ans;
struct Node {ll val, mask, bits;}a[N];

int main() {
	scanf("%llu", &n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld", &a[i].val, &a[i].mask);
		ans += a[i].val;
		for(ll _=bit;_+1;_--) if((a[i].mask >> _) & 1) {a[i].bits = _; break;}
	}
	if(ans < 0) for(ll i=1;i<=n;i++) a[i].val = -a[i].val;
	ans = 0;
	for(ll _=0;_<=bit;_++) {
		ll s = 0;
		for(ll i=1;i<=n;i++) s += (a[i].bits == _) * a[i].val;
		if(s <= 0) continue;
		ans |= (1LL << _);
		for(ll i=1;i<=n;i++) a[i].val *= ((a[i].mask >> _) & 1) ? -1 : 1;
	}
	printf("%lld\n", ans);
//	puts("----------\nDEBUG: "); for(ll i=1;i<=n;i++) printf("%lld\n", a[i].val);
	return 0;
}